package com.study;


import java.util.ArrayList;

//稠密图,邻接矩阵
public class DenseGraph {
    private int n;  //节点数
    private int e;  //图中的边数
    private boolean directed;   //是否为有向图
    private boolean[][] matrix; //邻接矩阵, false 表示没有边

    public DenseGraph(int n , boolean directed ){
        assert n > 0;

        this.n = n;
        this.e = 0;
        this.directed = directed;
        // boolean 默认是 false
        this.matrix = new boolean[n][n];
    }

    //返回节点的个数
    public int getN() {
        return n;
    }

    //返回边的个数
    public int getE() {
        return e;
    }

    public boolean isDirected() {
        return directed;
    }

    public boolean[][] getMatrix() {
        return matrix;
    }

    //向图中 ,b 节点添加一个边
    public void addEdge(int a, int b ){
        assert a>=0 && a<n;
        assert b>=0 && b<n;

        //如果已经有一条边了则不需要在添加了
        if( hasEdge(a,b) ){
            return;
        }

        this.matrix[a][b]=true;
        //如果是无向图的话，要相互加边
        if( !directed ){
            this.matrix[b][a]=true;
        }
        this.e++;  //无向图,不分方向。所以也是 加 1
    }

    //判断两个节点直接是否已经存在边
    public boolean hasEdge( int a, int b){
        assert a>=0 && a<n;
        assert b>=0 && b<n;

        return this.matrix[a][b];
    }

    //返回 v 点的所有邻接点的迭代器
    public Iterable<Integer> adj( int v ){
        checkBound(v);
        ArrayList<Integer> arrayList = new ArrayList<>();

        for ( int i=0; i < n; ++i ){
            if( matrix[v][i] ){
                arrayList.add(i);
            }
        }

        return arrayList;
    }

    //检查是否越界，越界抛出异常
    private void checkBound(int a ){
        if (a < 0 || a >= n ) {
            throw new ArrayIndexOutOfBoundsException("超过点的个数");
        }
    }


}
